МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
КОМП’ЮТЕРНА ГРАФІКА МЕТОДИЧНІ ВКАЗІВКИ до виконання лабораторної роботи № 7 Алгоритм Брезенхема для генерації кола для студентів бакалаврського рівня підготовки спеціальності «Комп‘ютерні науки» та «Видавничо-поліграфічна справа» Затверджено на засіданні кафедри Інформаційні технології видавничої справи Протокол № 5-11/12 від 23 грудня 2011 р. Львів – 2012 Алгоритм Брезенхема для генерації кола: Методичні вказівки до лабораторної роботи № 7 з курсу “Комп’ютерна графіка” для студентів «Видавничо-поліграфічна справа» (шифр - 0927) та “Комп‘ютерні науки” (шифр - 0804) / Укл.: О.Я. Різник - Львів: Видавництво Національного університету “Львівська політехніка”, 2012 - 14 с. Укладач: Різник О.Я., к.т.н., доц. Відповідальний за випуск: Різник О. Я., к. т. н., доц. Рецензент: Рашкевич Ю.М., д.т.н., проф. ЛАБОРАТОРНА РОБОТА № 7 АЛГОРИТМ БРЕЗЕНХЕМА ДЛЯ ГЕНЕРАЦІЇ КОЛА Мета роботи: Освоїти алгоритми побудови кола засобами комп’ютерної графіки ТЕОРЕТИЧНІ ВІДОМОСТІ У растр розкладають не тільки лінійні, але й інші, більш складні функції. Розкладанню конічних перетинів, тобто кіл, еліпсів, парабол, гіпербол було присвячено значне число робіт. Найбільша увага, зрозуміло, приділена колу. Один з найбільш ефективних і простих для розуміння алгоритмів генерації кола належить Брезенхему. Для початку відзначимо, що необхідно згенерувати тільки одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на рис. 7.1. Якщо згенерований перший октант (від 0 до 45° проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої y=х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х=0 для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої y=0 для завершення побудови. На рис.7.1 наведені двовимірні матриці відповідних перетворень.
Рис.7.1. Генерація повного кола з дуги в першому октанті Для виведення алгоритму розглянемо першу чверть кола з центром у початку координат. Помітимо, що якщо робота алгоритму починається в точці х=0, у=R, то при генерації кола за годинниковою стрілкою в першому квадранті у є монотонно спадною функцією аргумента х (рис.5.2). Аналогічно, якщо вихідною точкою є у=0, х=R, то при генерації кола проти годинникової стрілки х буде монотонно спадною функцією аргументу у. У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці х=0, у=R. Передбачається, що центр кола і початкова точка знаходяться точно в точках растра. Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, що щонайкраще наближає коло: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. На рис.7.3 ці напрямки позначені відповідно mH, mD, mV. Алгоритм вибирає піксел, для якого мінімальний квадрат відстані між одним з цих положень і колом, тобто мінімум з mH=|(xi+1)2+(yi)2-R2| mD=|(xi+1)2+(yi-1)2-R2| mV=|(xi)2+(yi-1)2-R2|

Рис. 7.2. Коло у першому квадранті Рис.7.3. Вибір пікселів у першому квадранті Обчислення можна спростити, якщо зауважити, що в околі точки (xi, yi) можливі тільки п’ять типів перетинів кола і сітки растра, наведених на рис.7.4.
Рис. 7.4. Перетини кола і сітки растра Різниця між квадратами відстаней від центра кола до діагонального піксела (xi+1, уi-1) і від центра до точки на колі R2 дорівнює: Di=(xi+1)2+(yi-1)2-R2 Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного піксела бажано використовувати тільки знак похибки, а не її величину. При Di<0 діагональна точка (xi+1, уi-1) знаходиться всередині реального кола, тобто це випадки 1 або 2 на рис. 7.4. Ясно, що в цій ситуації варто вибрати або піксел (xi+1, уi), тобто mH, або піксел (xi+1, уi-1), тобто mD. Для цього спочатку розглянемо випадок 1 і перевіримо різницю квад...